import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Test {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        //合并两个有序数组
        int size=nums1.length-1;
        m--;
        n--;
        while(m!=-1&&n!=-1) {
            if(nums1[m]<nums2[n]) {
                nums1[size]=nums2[n];
                n--;
            }else {
                nums1[size]=nums1[m];
                m--;
            }
            size--;
        }
        while (n!=-1) {
            nums1[size]=nums2[n];
            n--;
            size--;
        }
    }


    public int[] intersect2(int[] nums1, int[] nums2) {
        //桶排
        int[]array1=new int[1002];
        int[]array2=new int[1002];
        for (int i = 0; i < nums1.length; i++) {
            array1[nums1[i]]++;
        }
        for (int i = 0; i < nums2.length; i++) {
            array2[nums2[i]]++;
        }
        int size=0;
        int[]copy=new int[1002];
        for (int i = 0; i < array1.length; i++) {
            while (array1[i]!=0&&array2[i]!=0) {
                copy[size++]=i;
                array1[i]--;
                array2[i]--;
            }
        }
        copy= Arrays.copyOf(copy,size);
        return copy;
    }

    /**
     * 非递归快排
     * @param array
     */
    public static void quickSort1(int[]array) {
        Deque<Integer> deque=new ArrayDeque<>();
        int left=0;
        int right= array.length-1;
        deque.push(left);
        deque.push(right);
        while (!deque.isEmpty()) {
            right=deque.pop();
            left=deque.pop();
           int Index=func(array,left,right);
            if(left+1<Index) {
                deque.push(left);
                deque.push(Index-1);
            }
            if(Index+1<right) {
                deque.push(Index+1);
                deque.push(right);
            }
        }
    }

    /**
     * 递归快排
     * @param array
     */
    public static void quickSort(int[]array) {
      Quick(array,0,array.length-1);
    }
    //递归快排
    public static void Quick(int[] array,int left,int right) {
        if(left>=right) {
            return;
        }
        if(right-left+1<=20) {
            InsertSort(array,left,right);
            return;
        }
        //找出中间值
        int p=middleThree(array,left,right);
        swap(array,left,p);
        int Index=func(array,left,right);
        Quick(array,left,Index-1);
        Quick(array,Index+1,right);
    }
    public static void swap(int[]array,int left,int right) {
        int tmp=array[left];
        array[left]=array[right];
        array[right]=tmp;
    }
    public static int func(int[]array,int left,int right) {
        //交换法
        int tmp=array[left];
        int p=left;
        while (left<right) {
            while (left<right&&array[right]>=tmp) {
                right--;
            }
            while (left<right&&array[left]<=tmp) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,p,left);
        return left;
    }
    //三数求中
    public static int middleThree(int[]array,int left,int right) {
        int mid=(left+right+1)>>2;
        if(array[left]<array[right]) {
            if(array[mid]<array[left]) {
                return left;
            }else if(array[mid]>array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid]>array[left]) {
                return left;
            }else if(array[mid]<array[right]) {
                return right;
            }else {
                return mid;
            }
        }
    }
    //插入排序
    public static void InsertSort(int array[],int left,int right) {
        //插入排序
        for (int i = left+1; i <= right; i++) {
            int tmp=array[i];
            int j = i-1;
            for (; j >=left; j--) {
                if(array[j]>tmp) {
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

    public static int[] intersect(int[] nums1, int[] nums2) {
        //手写快排
        quickSort(nums1);
        quickSort(nums2);
        int i=0;
        int j=0;
        int size=0;
        int []array=new int[Math.max(nums1.length, nums2.length)];
        while (i< nums1.length&&j< nums2.length) {
            if(nums1[i]==nums2[j]) {
                array[size++]=nums1[i];
            }
            else if(nums1[i]<nums2[j]) {
                i++;
            }
            else  {
                j++;
            }
        }
        array= Arrays.copyOf(array,size);
        return array;
    }
    public static void main1(String[] args) {
        int[]array1={9,8,7,6,5,4,3,2,1};
        int[]array2={1,2,3};
        //quickSort(array1);
        quickSort1(array1);
        System.out.println("====");;
      //  merge(array1,3,array2,3);

        System.out.println(Arrays.toString(array1));
    }

    public static void main2(String[] args) {
        double n = 1;
        double num = 0;
        double sum = 0;
        System.out.println((long) (Math.pow(10,7)));
        while (true){

            num = 1/Math.pow(n,2);
            if(num < 1.0/(Math.pow(10,7))){
                System.out.println(n);
                break;
            }
            sum = sum + num;
            n++;
        }
        System.out.println(sum);
        System.out.printf("%.4f\n",sum);


    }

    /**
     * 选择排序
     * 时间复杂度O(n^2)
     *空间复杂度O(1)
     * 不稳定
     */
    public static void mySort(int[]b,int n){
        //一个变量不断向后,找到一个最小值
        for (int left = 0; left <= n-1; left++) {
            int min = left;
            for (int i = left+1;i < n;i++){
                if(b[min] > b[i]){
                    min = i;
                }
            }
            swap(b,left,min);

        }
        System.out.println(Arrays.toString(b));
    }

    public static void main8(String[] args) {
        int[]array = new int[1000];
        for (int i = 0; i < 1000; i++) {
            array[i] = 1000-i;
        }
        mySort(array, array.length);
    }

    public static void main(String[] args) {
        System.out.println(10^12);
        System.out.println(6^12);

    }
}
